package jutf8search;

import java.io.Serializable;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Vector;

/**
 * Implements the 'Counting' algorithm to perform Hamming distance mistmatching, using
 * the contract given by FuzzySearchInterface.
 * 
 *
 */
public class Counting implements FuzzySearchInterface, Serializable
{
    private byte[] query;
    private Hashtable<Integer, LinkedList<Integer>> charPos;
    private long match;

	/*
	 * (non-Javadoc)
	 * @see jutf8search.FuzzySearchInterface#preprocess(byte[])
	 */
	public void preprocess(byte[] query)
    {
        this.query = query;
        charPos = new Hashtable<Integer, LinkedList<Integer>>();
        for(int i=0; i<query.length; i++)
        {
            try
            {
                (charPos.get(new Integer(query[i]))).add(new Integer(i));
            }
            catch(NullPointerException e)
            {
                LinkedList<Integer> ll = new LinkedList<Integer>();
                ll.add(new Integer(i));
                charPos.put(new Integer(query[i]),ll);
            }
        }
        /* (debug) check the table */
        /*for(int i=0; i<query.length; i++)
        {
            System.out.print("byte value "+query[i]+" occurs at ");
            LinkedList<Integer> ll = charPos.get(new Integer(query[i]));
            for(int j=0; j<ll.size(); j++)
              System.out.print(ll.get(j)+",");
            System.out.println();
        }*/
    }
	
	/*
	 * (non-Javadoc)
	 * @see jutf8search.FuzzySearchInterface#preprocess(java.lang.String)
	 */
	public void preprocess(String query)
    {
		preprocess(Utilities.getBytes(query));
    }
	
	/*
	 * (non-Javadoc)
	 * @see jutf8search.FuzzySearchInterface#numMatches(byte[], int)
	 */
	public int numMatches(byte[] text, int distance)
    {
        int[] matchPos = new int[query.length];
        int[] scope = new int[query.length];
        int numMatches = 0;
        
        for(int i=0; i<text.length; i++)
        {
            LinkedList<Integer> ll = charPos.get(new Integer(text[i]));
            if(ll==null)
            {
                i+= Utilities.skipBytes(text[i])-1;
                continue;
            }
            for(int j=0; j<ll.size(); j++)
            {
                int p = i - ll.get(j).intValue();
                if(p<0) continue;
                int m = p % query.length;
                if(matchPos[m]==0)
                {
                    matchPos[m]++;
                    scope[m] = i;
                }
                else if(i >= scope[m]+query.length)
                {
                    matchPos[m] = 1;
                    scope[m] = i;
                }
                else
                    matchPos[m]++;
                if(matchPos[m]>=query.length-distance)
                    numMatches++;
            }
        }
        return numMatches;
    }
	
	/*
	 * (non-Javadoc)
	 * @see jutf8search.FuzzySearchInterface#matchNum(byte[], long, int)
	 */
	public int matchNum(byte[] text, long matchNum, int distance)
    {
        int[] matchPos = new int[query.length];
        int[] scope = new int[query.length];
        int t = -1;
        for(int i=0; i<text.length; i++)
        {
        	++t;
            LinkedList<Integer> ll = charPos.get(new Integer(text[i]));
            if(ll==null)
            {
                i+= Utilities.skipBytes(text[i])-1;
                continue;
            }
            for(int j=0; j<ll.size(); j++)
            {
                int p = t - ll.get(j).intValue();
                if(p<0) continue;
                int m = p % query.length;
                if(matchPos[m]==0)
                {
                    matchPos[m]++;
                    scope[m] = t;
                }
                else if(i >= scope[m]+query.length)
                {
                    matchPos[m] = 1;
                    scope[m] = t;
                }
                else
                    matchPos[m]++;
                if(matchPos[m]>=query.length-distance)
                {
                    match++;
                    if(match==matchNum) return p+1;
                }
            }
        }
        return -1;
    }
	
    /*
     * (non-Javadoc)
     * @see jutf8search.FuzzySearchInterface#fullSearch(byte[], int)
     */
	public Vector<Long> fullSearch(byte[] text, int distance)
    {
        int[] matchPos = new int[query.length];
        int[] scope = new int[query.length];
        Vector<Long> results = new Vector<Long>();
        
        for(int i=0; i<text.length; i++)
        {
            //System.out.print("matchPos: [");
            //for(int j=0; j<matchPos.length; j++) System.out.print(matchPos[j]+",");
            //System.out.println("]");
            
            LinkedList<Integer> ll = charPos.get(new Integer(text[i]));
            if(ll==null)
            {
                i+= Utilities.skipBytes(text[i])-1;
                continue;
            }

            //System.out.print("byte "+i+" matches with pattern at positions ");
            for(int j=0; j<ll.size(); j++)
            {
                //System.out.print(ll.get(j).intValue()+",");
                int p = i - ll.get(j).intValue();
                int m = p % query.length;
                if(p<0) continue;
                if(matchPos[m]==0)
                {
                    matchPos[m]++;
                    scope[m] = i;
                }
                else if(i >= scope[m]+query.length)
                {
                    matchPos[m] = 1;
                    scope[m] = i;
                }
                else
                {
                    matchPos[m]++;
                }
                if(matchPos[m]>=query.length-distance)
                    results.add(new Long(p+1));
            }
            //System.out.println();
        }
        return results;
    }

	/*
	 * (non-Javadoc)
	 * @see jutf8search.FuzzySearchInterface#getPatternSize()
	 */
	public int getPatternSize()
    {
        return query.length;
    }
	
	/*
	 * (non-Javadoc)
	 * @see jutf8search.FuzzySearchInterface#resetMatch()
	 */
	public void resetMatch()
    {
        match = 0;
    }
    
}
